package map;

import java.util.HashSet;
import java.util.Set;

/**
 * 36. 有效的数独
 */
public class IsValidSudoku {
    private static final int LEN = 9;
    public boolean isValidSudoku(char[][] board) {
//        return judgeRow(board, 0) && judgeCol(board, 0) && judgePart(board);

        // 一次遍历
        // 因为数字的范围只是从0到9所以直接用数组，而不用哈希表
        int[][] row = new int[LEN][LEN]; // row[i][j]:表示board的第i + 1行数字j + 1出现的次数
        int[][] col = new int[LEN][LEN]; // col[i][j]:表示board的第i + 1列数字j + 1出现的次数
        int[][][] part = new int[3][3][LEN]; // part[i][j][k]:表示board的i * 3, j * 3所在的九宫格，数字k + 1出现的次数
        for (int i = 0; i < LEN; i++) {
            for (int j = 0; j < LEN; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '1'; // 数字c的索引
                    int rowCount = ++ row[i][index];
                    int colCount = ++ col[index][j];
                    int partCount = ++ part[i / 3][j / 3][index];
                    if (rowCount > 1 || colCount > 1 || partCount > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     * 判断行是否符合要求
     * @param board
     * @param index 行数
     * @return
     */
    public boolean judgeRow(char[][] board, int index) {
        if (index >= LEN) {
            return true;
        }
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < LEN; i++) {
            char c = board[index][i];
            if (c != '.' && !set.add(c)) {
                return false;
            }
        }
        return judgeRow(board, index + 1);
    }

    /**
     * 判断列是否符合要求
     * @param board
     * @param index 列数
     * @return
     */
    public boolean judgeCol(char[][] board, int index) {
        if (index >= LEN) {
            return true;
        }
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < LEN; i++) {
            char c = board[i][index];
            if (c != '.' && !set.add(c)) {
                return false;
            }
        }
        return judgeCol(board, index + 1);
    }

    /**
     * 判断九个九宫格是否符合要求
     * @param board
     * @return
     */
    public boolean judgePart(char[][] board) {
        // 遍历数组，逐个创建九宫格数组并判断
        for (int i = 0; i < LEN; i += 3) {
            for (int j = 0; j < LEN; j += 3) {
                char[][] partBoard = new char[3][3];
                for (int k = 0; k < 3; k++) {
                    for (int l = 0; l < 3; l++) {
                        partBoard[k][l] = board[k + i][l + j];
                    }
                }
                if (!isTrue(partBoard)) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 判断一个九宫格是否符合要求
     * @param partBoard 3*3的数组
     * @return
     */
    public boolean isTrue(char[][] partBoard) {
        Set<Character> set = new HashSet<>();
        int len = partBoard.length;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                char part = partBoard[i][j];
                if (part != '.' && !set.add(part)) {
                    return false;
                }
            }
        }
        return true;
    }
}

class Test {
    public static void main(String[] args) {
        char[][] board = new char[][] {
                {'.','.','4','.','.','.','6','3','.'},
                {'.','.','.','.','.','.','.','.','.'},
                {'5','.','.','.','.','.','.','9','.'},
                {'.','.','.','5','6','.','.','.','.'},
                {'4','.','3','.','.','.','.','.','1'},
                {'.','.','.','7','.','.','.','.','.'},
                {'.','.','.','5','.','.','.','.','.'},
                {'.','.','.','.','.','.','.','.','.'},
                {'.','.','.','.','.','.','.','.','.'}
        };
        IsValidSudoku isValidSudoku = new IsValidSudoku();
        System.out.println(isValidSudoku.isValidSudoku(board));
    }
}

// [['.','.','4','.','.','.','6','3','.'],
//  ['.','.','.','.','.','.','.','.','.'],
//  ['5','.','.','.','.','.','.','9','.'],
//  ['.','.','.','5','6','.','.','.','.'],
//  ['4','.','3','.','.','.','.','.','1'],
//  ['.','.','.','7','.','.','.','.','.'],
//  ['.','.','.','5','.','.','.','.','.'],
//  ['.','.','.','.','.','.','.','.','.'],
//  ['.','.','.','.','.','.','.','.','.']]
